// 图（Graph）练习题参考答案（C语言实现）
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
#include <limits.h>

// ======================= 图的基本结构 =======================

// 邻接表节点结构
typedef struct AdjListNode {
    int dest;                // 目标顶点
    int weight;              // 边的权重
    struct AdjListNode* next; // 指向下一个邻接节点的指针
} AdjListNode;

// 邻接表结构
typedef struct AdjList {
    AdjListNode* head; // 邻接表头指针
} AdjList;

// 图结构
typedef struct Graph {
    int V;          // 顶点数
    AdjList* array; // 邻接表数组
    bool directed;  // 是否为有向图
} Graph;

// 创建新的邻接表节点
AdjListNode* newAdjListNode(int dest, int weight) {
    AdjListNode* newNode = (AdjListNode*)malloc(sizeof(AdjListNode));
    if (newNode == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    newNode->dest = dest;
    newNode->weight = weight;
    newNode->next = NULL;
    return newNode;
}

// 创建一个具有V个顶点的图
Graph* createGraph(int V, bool directed) {
    Graph* graph = (Graph*)malloc(sizeof(Graph));
    if (graph == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    graph->V = V;
    graph->directed = directed;
    
    // 为每个顶点分配一个邻接表
    graph->array = (AdjList*)malloc(V * sizeof(AdjList));
    if (graph->array == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有邻接表为空
    for (int i = 0; i < V; i++) {
        graph->array[i].head = NULL;
    }
    
    return graph;
}

// 向图中添加边
void addEdge(Graph* graph, int src, int dest, int weight) {
    // 添加一条从src到dest的边
    AdjListNode* newNode = newAdjListNode(dest, weight);
    newNode->next = graph->array[src].head;
    graph->array[src].head = newNode;
    
    // 如果是无向图，还要添加一条从dest到src的边
    if (!graph->directed) {
        newNode = newAdjListNode(src, weight);
        newNode->next = graph->array[dest].head;
        graph->array[dest].head = newNode;
    }
}

// 从图中删除边
void removeEdge(Graph* graph, int src, int dest) {
    // 处理src到dest的边
    AdjListNode* prev = NULL;
    AdjListNode* current = graph->array[src].head;
    
    // 找到要删除的边
    while (current != NULL && current->dest != dest) {
        prev = current;
        current = current->next;
    }
    
    // 如果找到要删除的边
    if (current != NULL) {
        if (prev == NULL) {
            // 要删除的是头节点
            graph->array[src].head = current->next;
        } else {
            prev->next = current->next;
        }
        free(current);
    }
    
    // 如果是无向图，还要删除dest到src的边
    if (!graph->directed) {
        prev = NULL;
        current = graph->array[dest].head;
        
        while (current != NULL && current->dest != src) {
            prev = current;
            current = current->next;
        }
        
        if (current != NULL) {
            if (prev == NULL) {
                graph->array[dest].head = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
        }
    }
}

// 检查两个顶点是否相邻
bool isAdjacent(Graph* graph, int src, int dest) {
    AdjListNode* current = graph->array[src].head;
    while (current != NULL) {
        if (current->dest == dest) {
            return true;
        }
        current = current->next;
    }
    return false;
}

// 打印图
void printGraph(Graph* graph) {
    for (int v = 0; v < graph->V; v++) {
        AdjListNode* pCrawl = graph->array[v].head;
        printf("顶点 %d 的邻接点: ", v);
        while (pCrawl) {
            printf("%d(%d) -> ", pCrawl->dest, pCrawl->weight);
            pCrawl = pCrawl->next;
        }
        printf("NULL\n");
    }
}

// 释放图的内存
void freeGraph(Graph* graph) {
    for (int i = 0; i < graph->V; i++) {
        AdjListNode* current = graph->array[i].head;
        while (current) {
            AdjListNode* next = current->next;
            free(current);
            current = next;
        }
    }
    free(graph->array);
    free(graph);
}

// ======================= 队列结构（用于BFS）=======================

typedef struct Queue {
    int* items;
    int front;
    int rear;
    int capacity;
} Queue;

// 创建队列
Queue* createQueue(int capacity) {
    Queue* queue = (Queue*)malloc(sizeof(Queue));
    queue->capacity = capacity;
    queue->front = queue->rear = -1;
    queue->items = (int*)malloc(capacity * sizeof(int));
    return queue;
}

// 检查队列是否为空
bool isQueueEmpty(Queue* queue) {
    return queue->front == -1;
}

// 检查队列是否已满
bool isQueueFull(Queue* queue) {
    return queue->rear == queue->capacity - 1;
}

// 入队操作
void enqueue(Queue* queue, int item) {
    if (isQueueFull(queue)) {
        printf("队列已满\n");
        return;
    }
    
    if (isQueueEmpty(queue)) {
        queue->front = 0;
    }
    
    queue->items[++queue->rear] = item;
}

// 出队操作
int dequeue(Queue* queue) {
    if (isQueueEmpty(queue)) {
        printf("队列为空\n");
        return -1;
    }
    
    int item = queue->items[queue->front];
    
    if (queue->front == queue->rear) {
        queue->front = queue->rear = -1;
    } else {
        queue->front++;
    }
    
    return item;
}

// 释放队列
void freeQueue(Queue* queue) {
    free(queue->items);
    free(queue);
}

// ======================= 栈结构（用于DFS和拓扑排序）=======================

typedef struct Stack {
    int* items;
    int top;
    int capacity;
} Stack;

// 创建栈
Stack* createStack(int capacity) {
    Stack* stack = (Stack*)malloc(sizeof(Stack));
    stack->capacity = capacity;
    stack->top = -1;
    stack->items = (int*)malloc(capacity * sizeof(int));
    return stack;
}

// 检查栈是否为空
bool isStackEmpty(Stack* stack) {
    return stack->top == -1;
}

// 检查栈是否已满
bool isStackFull(Stack* stack) {
    return stack->top == stack->capacity - 1;
}

// 入栈操作
void push(Stack* stack, int item) {
    if (isStackFull(stack)) {
        printf("栈已满\n");
        return;
    }
    stack->items[++stack->top] = item;
}

// 出栈操作
int pop(Stack* stack) {
    if (isStackEmpty(stack)) {
        printf("栈为空\n");
        return -1;
    }
    return stack->items[stack->top--];
}

// 获取栈顶元素
int peek(Stack* stack) {
    if (isStackEmpty(stack)) {
        printf("栈为空\n");
        return -1;
    }
    return stack->items[stack->top];
}

// 释放栈
void freeStack(Stack* stack) {
    free(stack->items);
    free(stack);
}

// ======================= 基础题解答 =======================

// 2. 深度优先搜索（DFS）辅助函数
void DFSUtil(Graph* graph, int v, bool visited[]) {
    // 标记当前顶点为已访问
    visited[v] = true;
    printf("%d ", v);
    
    // 递归访问所有未访问的邻接点
    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        int adj = pCrawl->dest;
        if (!visited[adj]) {
            DFSUtil(graph, adj, visited);
        }
        pCrawl = pCrawl->next;
    }
}

// 2. 深度优先搜索
void DFS(Graph* graph, int start) {
    // 创建一个访问标记数组
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    printf("DFS 遍历 (从顶点 %d 开始): ", start);
    DFSUtil(graph, start, visited);
    printf("\n");
    
    free(visited);
}

// 3. 广度优先搜索
void BFS(Graph* graph, int start) {
    // 创建一个访问标记数组
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    // 创建一个队列
    Queue* queue = createQueue(graph->V);
    
    // 标记起始顶点为已访问并入队
    visited[start] = true;
    enqueue(queue, start);
    
    printf("BFS 遍历 (从顶点 %d 开始): ", start);
    
    while (!isQueueEmpty(queue)) {
        // 出队一个顶点并访问
        int current = dequeue(queue);
        printf("%d ", current);
        
        // 将所有未访问的邻接点入队
        AdjListNode* pCrawl = graph->array[current].head;
        while (pCrawl) {
            int adj = pCrawl->dest;
            if (!visited[adj]) {
                visited[adj] = true;
                enqueue(queue, adj);
            }
            pCrawl = pCrawl->next;
        }
    }
    
    printf("\n");
    
    free(visited);
    freeQueue(queue);
}

// 4. 判断图是否连通
bool isConnected(Graph* graph) {
    if (graph->directed) {
        printf("错误：isConnected函数仅适用于无向图\n");
        return false;
    }
    
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    // 从第一个非孤立顶点开始DFS
    int start = 0;
    while (start < graph->V && graph->array[start].head == NULL) {
        start++;
    }
    
    // 如果所有顶点都是孤立的，图是连通的
    if (start == graph->V) {
        free(visited);
        return true;
    }
    
    // 进行DFS
    DFSUtil(graph, start, visited);
    
    // 检查是否所有顶点都被访问
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i] && graph->array[i].head != NULL) {
            free(visited);
            return false;
        }
    }
    
    free(visited);
    return true;
}

// 5. 计算连通分量的数量
int countConnectedComponents(Graph* graph) {
    if (graph->directed) {
        printf("错误：countConnectedComponents函数仅适用于无向图\n");
        return -1;
    }
    
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    int count = 0;
    
    // 对每个未访问的顶点进行DFS
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i] && graph->array[i].head != NULL) {
            count++;
            DFSUtil(graph, i, visited);
        }
    }
    
    free(visited);
    return count;
}

// 6. 找出图中的路径（使用DFS）
bool findPathUtil(Graph* graph, int current, int end, bool visited[], int path[], int* pathLength) {
    // 标记当前顶点为已访问并添加到路径中
    visited[current] = true;
    path[*pathLength] = current;
    (*pathLength)++;
    
    // 如果到达终点，返回true
    if (current == end) {
        return true;
    }
    
    // 递归访问所有未访问的邻接点
    AdjListNode* pCrawl = graph->array[current].head;
    while (pCrawl) {
        int adj = pCrawl->dest;
        if (!visited[adj]) {
            if (findPathUtil(graph, adj, end, visited, path, pathLength)) {
                return true;
            }
        }
        pCrawl = pCrawl->next;
    }
    
    // 如果从当前顶点无法到达终点，从路径中移除当前顶点
    (*pathLength)--;
    return false;
}

bool findPath(Graph* graph, int start, int end, int path[], int* pathLength) {
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    *pathLength = 0;
    bool found = findPathUtil(graph, start, end, visited, path, pathLength);
    
    free(visited);
    return found;
}

// ======================= 提高题解答 =======================

// 7. 检测无向图中的环（辅助函数）
bool isCyclicUndirectedUtil(Graph* graph, int v, bool visited[], int parent) {
    visited[v] = true;
    
    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        int adj = pCrawl->dest;
        
        // 如果邻接点未访问，递归检查
        if (!visited[adj]) {
            if (isCyclicUndirectedUtil(graph, adj, visited, v)) {
                return true;
            }
        }
        // 如果邻接点已访问且不是父节点，则存在环
        else if (adj != parent) {
            return true;
        }
        
        pCrawl = pCrawl->next;
    }
    
    return false;
}

// 7. 检测无向图中的环
bool isCyclicUndirected(Graph* graph) {
    if (graph->directed) {
        printf("错误：isCyclicUndirected函数仅适用于无向图\n");
        return false;
    }
    
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    // 对每个未访问的顶点进行检查
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i] && graph->array[i].head != NULL) {
            if (isCyclicUndirectedUtil(graph, i, visited, -1)) {
                free(visited);
                return true;
            }
        }
    }
    
    free(visited);
    return false;
}

// 8. 检测有向图中的环（辅助函数）
bool isCyclicDirectedUtil(Graph* graph, int v, bool visited[], bool recStack[]) {
    if (!visited[v]) {
        // 标记当前顶点为已访问并加入递归栈
        visited[v] = true;
        recStack[v] = true;
        
        // 递归检查所有邻接点
        AdjListNode* pCrawl = graph->array[v].head;
        while (pCrawl) {
            int adj = pCrawl->dest;
            
            // 如果邻接点未访问且从邻接点可以回到当前路径，存在环
            if (!visited[adj] && isCyclicDirectedUtil(graph, adj, visited, recStack)) {
                return true;
            }
            // 如果邻接点已在递归栈中，存在环
            else if (recStack[adj]) {
                return true;
            }
            
            pCrawl = pCrawl->next;
        }
    }
    
    // 回溯时从递归栈中移除当前顶点
    recStack[v] = false;
    return false;
}

// 8. 检测有向图中的环
bool isCyclicDirected(Graph* graph) {
    if (!graph->directed) {
        printf("错误：isCyclicDirected函数仅适用于有向图\n");
        return false;
    }
    
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    bool* recStack = (bool*)malloc(graph->V * sizeof(bool));
    if (visited == NULL || recStack == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
        recStack[i] = false;
    }
    
    // 对每个未访问的顶点进行检查
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i] && graph->array[i].head != NULL) {
            if (isCyclicDirectedUtil(graph, i, visited, recStack)) {
                free(visited);
                free(recStack);
                return true;
            }
        }
    }
    
    free(visited);
    free(recStack);
    return false;
}

// 9. 拓扑排序（辅助函数）
void topologicalSortUtil(Graph* graph, int v, bool visited[], Stack* stack) {
    visited[v] = true;
    
    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        int adj = pCrawl->dest;
        if (!visited[adj]) {
            topologicalSortUtil(graph, adj, visited, stack);
        }
        pCrawl = pCrawl->next;
    }
    
    // 将顶点压入栈中
    push(stack, v);
}

// 9. 拓扑排序
void topologicalSort(Graph* graph) {
    if (!graph->directed) {
        printf("错误：拓扑排序仅适用于有向图\n");
        return;
    }
    
    // 检查图中是否存在环
    if (isCyclicDirected(graph)) {
        printf("错误：图中存在环，无法进行拓扑排序\n");
        return;
    }
    
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    Stack* stack = createStack(graph->V);
    if (visited == NULL || stack == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    // 对每个未访问的顶点调用辅助函数
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i] && graph->array[i].head != NULL) {
            topologicalSortUtil(graph, i, visited, stack);
        }
    }
    
    // 输出拓扑排序结果
    printf("拓扑排序结果: ");
    while (!isStackEmpty(stack)) {
        printf("%d ", pop(stack));
    }
    printf("\n");
    
    free(visited);
    freeStack(stack);
}

// 10. 无权图的最短路径
void shortestPathUnweighted(Graph* graph, int start) {
    int* dist = (int*)malloc(graph->V * sizeof(int));
    if (dist == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化距离数组
    for (int i = 0; i < graph->V; i++) {
        dist[i] = -1; // -1 表示不可达
    }
    
    Queue* queue = createQueue(graph->V);
    
    // 设置起始顶点的距离为0并入队
    dist[start] = 0;
    enqueue(queue, start);
    
    while (!isQueueEmpty(queue)) {
        int current = dequeue(queue);
        
        // 更新所有邻接点的距离
        AdjListNode* pCrawl = graph->array[current].head;
        while (pCrawl) {
            int adj = pCrawl->dest;
            if (dist[adj] == -1) { // 如果邻接点未访问
                dist[adj] = dist[current] + 1;
                enqueue(queue, adj);
            }
            pCrawl = pCrawl->next;
        }
    }
    
    // 输出最短路径
    printf("从顶点 %d 到所有顶点的最短路径长度: \n", start);
    for (int i = 0; i < graph->V; i++) {
        printf("顶点 %d: %d\n", i, dist[i]);
    }
    
    free(dist);
    freeQueue(queue);
}

// 11. Dijkstra算法 - 单源最短路径
void dijkstra(Graph* graph, int src) {
    // 距离数组，初始化为无穷大
    int* dist = (int*)malloc(graph->V * sizeof(int));
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (dist == NULL || visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    for (int i = 0; i < graph->V; i++) {
        dist[i] = INT_MAX;
        visited[i] = false;
    }
    
    // 源点到自身的距离为0
    dist[src] = 0;
    
    // 找到所有顶点的最短路径
    for (int count = 0; count < graph->V - 1; count++) {
        // 找到未访问顶点中距离最小的顶点
        int minDist = INT_MAX, u;
        for (int v = 0; v < graph->V; v++) {
            if (!visited[v] && dist[v] <= minDist) {
                minDist = dist[v];
                u = v;
            }
        }
        
        // 标记该顶点为已访问
        visited[u] = true;
        
        // 松弛操作：更新所有邻接点的距离
        AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl) {
            int v = pCrawl->dest;
            int weight = pCrawl->weight;
            
            if (!visited[v] && dist[u] != INT_MAX && 
                dist[u] + weight < dist[v]) {
                dist[v] = dist[u] + weight;
            }
            
            pCrawl = pCrawl->next;
        }
    }
    
    // 输出最短路径
    printf("Dijkstra算法 - 从顶点 %d 到所有顶点的最短路径: \n", src);
    printf("顶点\t距离\n");
    for (int i = 0; i < graph->V; i++) {
        if (dist[i] == INT_MAX) {
            printf("%d\t不可达\n", i);
        } else {
            printf("%d\t%d\n", i, dist[i]);
        }
    }
    
    free(dist);
    free(visited);
}

// 12. Prim算法 - 最小生成树
void primMST(Graph* graph) {
    if (graph->directed) {
        printf("错误：Prim算法仅适用于无向图\n");
        return;
    }
    
    int* key = (int*)malloc(graph->V * sizeof(int));        // 存储顶点到MST的最小权重
    int* parent = (int*)malloc(graph->V * sizeof(int));     // 存储MST中顶点的父节点
    bool* mstSet = (bool*)malloc(graph->V * sizeof(bool));  // 标记顶点是否已在MST中
    
    if (key == NULL || parent == NULL || mstSet == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化
    for (int i = 0; i < graph->V; i++) {
        key[i] = INT_MAX;
        parent[i] = -1;
        mstSet[i] = false;
    }
    
    // 选择第一个顶点
    key[0] = 0;
    
    for (int count = 0; count < graph->V - 1; count++) {
        // 找到key值最小的顶点
        int minKey = INT_MAX, u;
        for (int v = 0; v < graph->V; v++) {
            if (!mstSet[v] && key[v] < minKey) {
                minKey = key[v];
                u = v;
            }
        }
        
        // 将顶点加入MST
        mstSet[u] = true;
        
        // 更新相邻顶点的key值
        AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl) {
            int v = pCrawl->dest;
            int weight = pCrawl->weight;
            
            if (!mstSet[v] && weight < key[v]) {
                parent[v] = u;
                key[v] = weight;
            }
            
            pCrawl = pCrawl->next;
        }
    }
    
    // 打印MST
    printf("Prim算法 - 最小生成树的边:\n");
    printf("边   \t权重\n");
    int totalWeight = 0;
    for (int i = 1; i < graph->V; i++) {
        printf("%d-%d\t%d\n", parent[i], i, key[i]);
        totalWeight += key[i];
    }
    printf("最小生成树总权重: %d\n", totalWeight);
    
    free(key);
    free(parent);
    free(mstSet);
}

// ======================= 挑战题解答 =======================

// 13. Bellman-Ford算法 - 处理负权边和检测负权环
void bellmanFord(Graph* graph, int src) {
    int* dist = (int*)malloc(graph->V * sizeof(int));
    if (dist == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化距离数组
    for (int i = 0; i < graph->V; i++) {
        dist[i] = INT_MAX;
    }
    dist[src] = 0;
    
    // 对所有边进行V-1次松弛操作
    for (int i = 0; i < graph->V - 1; i++) {
        for (int u = 0; u < graph->V; u++) {
            AdjListNode* pCrawl = graph->array[u].head;
            while (pCrawl) {
                int v = pCrawl->dest;
                int weight = pCrawl->weight;
                
                if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                    dist[v] = dist[u] + weight;
                }
                
                pCrawl = pCrawl->next;
            }
        }
    }
    
    // 检测负权环
    bool hasNegativeCycle = false;
    for (int u = 0; u < graph->V; u++) {
        AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl) {
            int v = pCrawl->dest;
            int weight = pCrawl->weight;
            
            if (dist[u] != INT_MAX && dist[u] + weight < dist[v]) {
                hasNegativeCycle = true;
                break;
            }
            
            pCrawl = pCrawl->next;
        }
        if (hasNegativeCycle) {
            break;
        }
    }
    
    if (hasNegativeCycle) {
        printf("警告：图中存在负权环\n");
    } else {
        // 输出最短路径
        printf("Bellman-Ford算法 - 从顶点 %d 到所有顶点的最短路径: \n", src);
        for (int i = 0; i < graph->V; i++) {
            if (dist[i] == INT_MAX) {
                printf("顶点 %d: 不可达\n", i);
            } else {
                printf("顶点 %d: %d\n", i, dist[i]);
            }
        }
    }
    
    free(dist);
}

// 14. Floyd-Warshall算法 - 所有顶点对最短路径
void floydWarshall(Graph* graph) {
    // 创建距离矩阵
    int** dist = (int**)malloc(graph->V * sizeof(int*));
    if (dist == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    for (int i = 0; i < graph->V; i++) {
        dist[i] = (int*)malloc(graph->V * sizeof(int));
        if (dist[i] == NULL) {
            printf("内存分配失败\n");
            exit(1);
        }
    }
    
    // 初始化距离矩阵
    for (int i = 0; i < graph->V; i++) {
        for (int j = 0; j < graph->V; j++) {
            if (i == j) {
                dist[i][j] = 0;
            } else {
                dist[i][j] = INT_MAX;
            }
        }
    }
    
    // 添加直接边
    for (int u = 0; u < graph->V; u++) {
        AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl) {
            int v = pCrawl->dest;
            int weight = pCrawl->weight;
            dist[u][v] = weight;
            pCrawl = pCrawl->next;
        }
    }
    
    // Floyd-Warshall算法主体
    for (int k = 0; k < graph->V; k++) {  // 中间顶点
        for (int i = 0; i < graph->V; i++) {  // 起点
            for (int j = 0; j < graph->V; j++) {  // 终点
                if (dist[i][k] != INT_MAX && dist[k][j] != INT_MAX && 
                    dist[i][k] + dist[k][j] < dist[i][j]) {
                    dist[i][j] = dist[i][k] + dist[k][j];
                }
            }
        }
    }
    
    // 输出所有顶点对之间的最短路径
    printf("Floyd-Warshall算法 - 所有顶点对之间的最短路径: \n");
    printf("\t");
    for (int i = 0; i < graph->V; i++) {
        printf("顶点%d\t", i);
    }
    printf("\n");
    
    for (int i = 0; i < graph->V; i++) {
        printf("顶点%d\t", i);
        for (int j = 0; j < graph->V; j++) {
            if (dist[i][j] == INT_MAX) {
                printf("INF\t");
            } else {
                printf("%d\t", dist[i][j]);
            }
        }
        printf("\n");
    }
    
    // 释放内存
    for (int i = 0; i < graph->V; i++) {
        free(dist[i]);
    }
    free(dist);
}

// 17. Kosaraju算法 - 强连通分量（简化版本）
void fillOrder(Graph* graph, int v, bool visited[], Stack* stack) {
    visited[v] = true;
    
    AdjListNode* pCrawl = graph->array[v].head;
    while (pCrawl) {
        int adj = pCrawl->dest;
        if (!visited[adj]) {
            fillOrder(graph, adj, visited, stack);
        }
        pCrawl = pCrawl->next;
    }
    
    push(stack, v);
}

void DFSUtilTransposed(Graph* transposedGraph, int v, bool visited[], int component[], int componentNum) {
    visited[v] = true;
    component[v] = componentNum;
    
    AdjListNode* pCrawl = transposedGraph->array[v].head;
    while (pCrawl) {
        int adj = pCrawl->dest;
        if (!visited[adj]) {
            DFSUtilTransposed(transposedGraph, adj, visited, component, componentNum);
        }
        pCrawl = pCrawl->next;
    }
}

void kosaraju(Graph* graph) {
    if (!graph->directed) {
        printf("错误：Kosaraju算法仅适用于有向图\n");
        return;
    }
    
    Stack* stack = createStack(graph->V);
    bool* visited = (bool*)malloc(graph->V * sizeof(bool));
    if (stack == NULL || visited == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未访问
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    // 第一次DFS，填充栈
    for (int i = 0; i < graph->V; i++) {
        if (!visited[i] && graph->array[i].head != NULL) {
            fillOrder(graph, i, visited, stack);
        }
    }
    
    // 创建转置图
    Graph* transposedGraph = createGraph(graph->V, true);
    for (int v = 0; v < graph->V; v++) {
        AdjListNode* pCrawl = graph->array[v].head;
        while (pCrawl) {
            addEdge(transposedGraph, pCrawl->dest, v, pCrawl->weight);
            pCrawl = pCrawl->next;
        }
    }
    
    // 重置访问数组
    for (int i = 0; i < graph->V; i++) {
        visited[i] = false;
    }
    
    // 存储每个顶点所属的强连通分量
    int* component = (int*)malloc(graph->V * sizeof(int));
    if (component == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    int componentNum = 0;
    
    // 第二次DFS，按栈的顺序处理顶点
    while (!isStackEmpty(stack)) {
        int v = pop(stack);
        if (!visited[v]) {
            DFSUtilTransposed(transposedGraph, v, visited, component, componentNum);
            componentNum++;
        }
    }
    
    // 输出强连通分量
    printf("Kosaraju算法 - 强连通分量: \n");
    for (int i = 0; i < componentNum; i++) {
        printf("分量 %d: ", i + 1);
        for (int j = 0; j < graph->V; j++) {
            if (component[j] == i) {
                printf("%d ", j);
            }
        }
        printf("\n");
    }
    
    // 释放内存
    free(visited);
    free(component);
    freeStack(stack);
    freeGraph(transposedGraph);
}

// 20. 二分图检测
bool isBipartiteUtil(Graph* graph, int v, int color[]) {
    color[v] = 1;  // 给当前顶点着色为1
    
    Queue* queue = createQueue(graph->V);
    enqueue(queue, v);
    
    while (!isQueueEmpty(queue)) {
        int u = dequeue(queue);
        
        // 检查所有邻接点
        AdjListNode* pCrawl = graph->array[u].head;
        while (pCrawl) {
            int adj = pCrawl->dest;
            
            // 如果邻接点未着色，着相反的颜色
            if (color[adj] == -1) {
                color[adj] = 1 - color[u];
                enqueue(queue, adj);
            }
            // 如果邻接点已经着色且颜色相同，不是二分图
            else if (color[adj] == color[u]) {
                freeQueue(queue);
                return false;
            }
            
            pCrawl = pCrawl->next;
        }
    }
    
    freeQueue(queue);
    return true;
}

bool isBipartite(Graph* graph) {
    int* color = (int*)malloc(graph->V * sizeof(int));
    if (color == NULL) {
        printf("内存分配失败\n");
        exit(1);
    }
    
    // 初始化所有顶点为未着色（-1）
    for (int i = 0; i < graph->V; i++) {
        color[i] = -1;
    }
    
    // 对每个未着色的顶点进行检查
    for (int i = 0; i < graph->V; i++) {
        if (color[i] == -1 && graph->array[i].head != NULL) {
            if (!isBipartiteUtil(graph, i, color)) {
                free(color);
                return false;
            }
        }
    }
    
    free(color);
    return true;
}

// ======================= 测试函数 =======================

void testBasicOperations() {
    printf("\n===== 测试基础操作 =====\n");
    Graph* graph = createGraph(5, false); // 5个顶点的无向图
    
    addEdge(graph, 0, 1, 1);
    addEdge(graph, 0, 2, 1);
    addEdge(graph, 1, 3, 1);
    addEdge(graph, 2, 3, 1);
    addEdge(graph, 2, 4, 1);
    
    printf("原始图:\n");
    printGraph(graph);
    
    printf("顶点0和1是否相邻: %s\n", isAdjacent(graph, 0, 1) ? "是" : "否");
    printf("顶点1和4是否相邻: %s\n", isAdjacent(graph, 1, 4) ? "是" : "否");
    
    removeEdge(graph, 0, 2);
    printf("删除边0-2后:\n");
    printf("顶点0和2是否相邻: %s\n", isAdjacent(graph, 0, 2) ? "是" : "否");
    
    freeGraph(graph);
}

void testTraversal() {
    printf("\n===== 测试遍历算法 =====\n");
    Graph* graph = createGraph(5, false);
    
    addEdge(graph, 0, 1, 1);
    addEdge(graph, 0, 2, 1);
    addEdge(graph, 1, 3, 1);
    addEdge(graph, 2, 3, 1);
    addEdge(graph, 2, 4, 1);
    
    DFS(graph, 0);
    BFS(graph, 0);
    
    freeGraph(graph);
}

void testConnectivity() {
    printf("\n===== 测试连通性 =====\n");
    
    // 连通图
    Graph* connectedGraph = createGraph(4, false);
    addEdge(connectedGraph, 0, 1, 1);
    addEdge(connectedGraph, 1, 2, 1);
    addEdge(connectedGraph, 2, 3, 1);
    
    printf("连通图测试: %s\n", isConnected(connectedGraph) ? "是连通图" : "不是连通图");
    freeGraph(connectedGraph);
    
    // 非连通图
    Graph* disconnectedGraph = createGraph(4, false);
    addEdge(disconnectedGraph, 0, 1, 1);
    addEdge(disconnectedGraph, 2, 3, 1);
    
    printf("非连通图测试: %s\n", isConnected(disconnectedGraph) ? "是连通图" : "不是连通图");
    printf("连通分量数量: %d\n", countConnectedComponents(disconnectedGraph));
    
    freeGraph(disconnectedGraph);
}

void testPathFinding() {
    printf("\n===== 测试路径查找 =====\n");
    Graph* graph = createGraph(5, false);
    
    addEdge(graph, 0, 1, 1);
    addEdge(graph, 1, 2, 1);
    addEdge(graph, 2, 3, 1);
    addEdge(graph, 0, 4, 1);
    
    int path[10];
    int pathLength;
    
    if (findPath(graph, 0, 3, path, &pathLength)) {
        printf("从顶点0到顶点3的路径: ");
        for (int i = 0; i < pathLength; i++) {
            printf("%d", path[i]);
            if (i < pathLength - 1) {
                printf(" -> ");
            }
        }
        printf("\n");
    } else {
        printf("从顶点0到顶点3没有路径\n");
    }
    
    freeGraph(graph);
}

void testCycleDetection() {
    printf("\n===== 测试环检测 =====\n");
    
    // 无向图环检测
    Graph* cyclicUndirected = createGraph(3, false);
    addEdge(cyclicUndirected, 0, 1, 1);
    addEdge(cyclicUndirected, 1, 2, 1);
    addEdge(cyclicUndirected, 2, 0, 1);
    
    printf("无向图是否有环: %s\n", isCyclicUndirected(cyclicUndirected) ? "是" : "否");
    freeGraph(cyclicUndirected);
    
    // 有向图环检测
    Graph* cyclicDirected = createGraph(3, true);
    addEdge(cyclicDirected, 0, 1, 1);
    addEdge(cyclicDirected, 1, 2, 1);
    addEdge(cyclicDirected, 2, 0, 1);
    
    printf("有向图是否有环: %s\n", isCyclicDirected(cyclicDirected) ? "是" : "否");
    freeGraph(cyclicDirected);
}

void testTopologicalSort() {
    printf("\n===== 测试拓扑排序 =====\n");
    Graph* graph = createGraph(4, true);
    
    addEdge(graph, 0, 1, 1);
    addEdge(graph, 0, 2, 1);
    addEdge(graph, 1, 3, 1);
    addEdge(graph, 2, 3, 1);
    
    topologicalSort(graph);
    
    freeGraph(graph);
}

void testShortestPath() {
    printf("\n===== 测试最短路径 =====\n");
    
    // 无权图最短路径
    Graph* unweightedGraph = createGraph(5, false);
    addEdge(unweightedGraph, 0, 1, 1);
    addEdge(unweightedGraph, 0, 2, 1);
    addEdge(unweightedGraph, 1, 3, 1);
    addEdge(unweightedGraph, 2, 3, 1);
    addEdge(unweightedGraph, 2, 4, 1);
    
    shortestPathUnweighted(unweightedGraph, 0);
    freeGraph(unweightedGraph);
    
    // Dijkstra算法
    Graph* weightedGraph = createGraph(4, true);
    addEdge(weightedGraph, 0, 1, 4);
    addEdge(weightedGraph, 0, 2, 2);
    addEdge(weightedGraph, 1, 3, 5);
    addEdge(weightedGraph, 2, 1, 1);
    addEdge(weightedGraph, 2, 3, 8);
    
    dijkstra(weightedGraph, 0);
    freeGraph(weightedGraph);
    
    // Bellman-Ford算法
    Graph* negativeWeightGraph = createGraph(4, true);
    addEdge(negativeWeightGraph, 0, 1, 5);
    addEdge(negativeWeightGraph, 0, 2, 2);
    addEdge(negativeWeightGraph, 1, 2, -10);
    addEdge(negativeWeightGraph, 2, 3, 3);
    
    bellmanFord(negativeWeightGraph, 0);
    freeGraph(negativeWeightGraph);
}

void testMST() {
    printf("\n===== 测试最小生成树 =====\n");
    Graph* graph = createGraph(4, false);
    
    addEdge(graph, 0, 1, 2);
    addEdge(graph, 0, 2, 3);
    addEdge(graph, 1, 2, 1);
    addEdge(graph, 1, 3, 4);
    addEdge(graph, 2, 3, 5);
    
    primMST(graph);
    
    freeGraph(graph);
}

void testAdvancedAlgorithms() {
    printf("\n===== 测试高级算法 =====\n");
    
    // Floyd-Warshall算法
    Graph* graph = createGraph(4, true);
    addEdge(graph, 0, 1, 3);
    addEdge(graph, 0, 2, 8);
    addEdge(graph, 1, 2, 4);
    addEdge(graph, 1, 3, 1);
    addEdge(graph, 2, 3, -5);
    
    floydWarshall(graph);
    freeGraph(graph);
    
    // Kosaraju算法（强连通分量）
    Graph* directedGraph = createGraph(5, true);
    addEdge(directedGraph, 0, 1, 1);
    addEdge(directedGraph, 1, 2, 1);
    addEdge(directedGraph, 2, 0, 1);
    addEdge(directedGraph, 2, 3, 1);
    addEdge(directedGraph, 3, 4, 1);
    addEdge(directedGraph, 4, 3, 1);
    
    kosaraju(directedGraph);
    freeGraph(directedGraph);
    
    // 二分图检测
    Graph* bipartiteGraph = createGraph(4, false);
    addEdge(bipartiteGraph, 0, 1, 1);
    addEdge(bipartiteGraph, 0, 3, 1);
    addEdge(bipartiteGraph, 1, 2, 1);
    addEdge(bipartiteGraph, 2, 3, 1);
    
    printf("图是否为二分图: %s\n", isBipartite(bipartiteGraph) ? "是" : "否");
    freeGraph(bipartiteGraph);
}

int main() {
    printf("===== 图数据结构练习题测试 =====\n\n");
    
    // 测试基础功能
    testBasicOperations();
    testTraversal();
    testConnectivity();
    testPathFinding();
    
    // 测试提高题
    testCycleDetection();
    testTopologicalSort();
    testShortestPath();
    testMST();
    
    // 测试挑战题
    testAdvancedAlgorithms();
    
    printf("\n===== 所有测试完成 =====\n");
    return 0;
}

/*
## 代码说明

### 数据结构定义
- **图的邻接表表示**：使用 `Graph`、`AdjList` 和 `AdjListNode` 结构
- **队列结构**：用于广度优先搜索（BFS）
- **栈结构**：用于深度优先搜索（DFS）和拓扑排序

### 基础题实现
1. **图的基本操作**：创建图、添加边、删除边、检查邻接关系
2. **深度优先搜索（DFS）**：递归实现，输出遍历顺序
3. **广度优先搜索（BFS）**：使用队列实现，输出遍历顺序
4. **连通性检查**：使用DFS判断无向图是否连通
5. **连通分量计数**：使用DFS计算无向图中的连通分量数量
6. **路径查找**：使用DFS找出从起点到终点的一条路径

### 提高题实现
7. **无向图环检测**：使用DFS，记录父节点避免误判
8. **有向图环检测**：使用DFS和递归栈
9. **拓扑排序**：基于DFS，将顶点按完成顺序压入栈中
10. **无权图最短路径**：使用BFS实现
11. **Dijkstra算法**：处理非负权边的单源最短路径
12. **Prim算法**：构建最小生成树

### 挑战题实现
13. **Bellman-Ford算法**：处理可能有负权边的最短路径，检测负权环
14. **Floyd-Warshall算法**：计算所有顶点对之间的最短路径
17. **Kosaraju算法**：找出有向图中的强连通分量
20. **二分图检测**：使用BFS给顶点着色，判断是否可以分成两个独立集

### 使用提示

1. 代码实现了练习中的大部分算法，每个算法都有详细的注释
2. 主函数中包含了各个算法的测试代码，展示如何使用这些实现
3. 对于较大的图，可能需要调整队列和栈的大小
4. 为了简化实现，一些边界情况的处理可能不够完善，实际应用中需要根据具体需求进行改进
5. 对于未实现的挑战题（如割点和桥、最大流、哈密顿路径、欧拉回路等），可以基于现有代码进行扩展

### 测试用例

代码中包含了全面的测试用例，覆盖了各种算法和场景：
- 基本操作测试
- 图的遍历（DFS和BFS）
- 连通性测试
- 路径查找测试
- 环检测测试
- 拓扑排序测试
- 各种最短路径算法测试
- 最小生成树测试
- 高级算法测试

通过这些测试，可以验证算法的正确性和理解算法的工作原理。*/
